home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Loadstar 12
/
012.d81
/
gcd article
< prev
next >
Wrap
Text File
|
2022-08-26
|
1KB
|
94 lines
THE GCD OF TWO INTEGERS
DEFINITION: The GREATEST COMMON
DIVISOR (GCD) of two integers, A and
B, is an integer D which satisfies the
following two criteria:
i) D divides A and D divides B.
ii) if D' is any other divisor of
both A and B, then D' also
divides D.
We use the notation (A,B) to denote
the GCD of A and B.
Repeated use of the Euclidean
Algorithm provides a method for
finding the GCD of two positive
integers.
THEOREM: Let A and B be two positive
integers. Then the following
algorithm results in the GCD of A and
B:
Assume, without loss of generality,
that B<A. Then applying the Euclidean
Algorithm, there exist unique integers
C and D such that
A = CB + D, 0 <= D < B.
If D=0, then B is the GCD of A and B.
If D#0, then divide B by D.
B = ED + F 0 <= F < D
Now divide D by F.
D = GF + H 0 <= H < F
Continuing in this way, always
dividing the divisor by the remainder,
we get a STRICTLY decreasing sequence
of remainders which must eventually
end with 0 (because the integers are
well-ordered).
Then the last non-zero remainder is
the GCD of A and B.
EXAMPLE: Let A=168 and B=30. Find the
GCD and LCM.
168 = (30)(5) + 18
30 = (18)(1) + 12
18 = (12)(1) + 6
12 = (2)(6)
The GCD is 6.
The LCM is (168)(30)/6 = 840.
Press '\' if you would like to run
\oad "gcd",8
GCD now.
--------------------------------------